//给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 
//
// 如果数组中不存在目标值 target，返回 [-1, -1]。 
//
// 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [5,7,7,8,8,10], target = 8
//输出：[3,4] 
//
// 示例 2： 
//
// 
//输入：nums = [5,7,7,8,8,10], target = 6
//输出：[-1,-1] 
//
// 示例 3： 
//
// 
//输入：nums = [], target = 0
//输出：[-1,-1] 
//
// 
//
// 提示： 
//
// 
// 0 <= nums.length <= 10⁵ 
// -10⁹ <= nums[i] <= 10⁹ 
// nums 是一个非递减数组 
// -10⁹ <= target <= 10⁹ 
// 
//
// Related Topics 数组 二分查找 👍 2595 👎 0


package com.tyrone.leetcode.editor.cn;

public class FindFirstAndLastPositionOfElementInSortedArray {
    public static void main(String[] args) {
        Solution solution = new FindFirstAndLastPositionOfElementInSortedArray().new Solution();
        System.out.println(solution.searchRange(new int[]{2,2}, 2));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {


        /**
         * 参考一下网上的 用两次二分 起坐标为第一次大于等于target的坐标，止坐标为第一次大于target的坐标
         * @param nums
         * @param target
         * @return
         */
        public int[] searchRange(int[] nums, int target) {
            int left = binarySearch(nums, target, true);
            int right = binarySearch(nums, target, false)-1;
            if (left <= right && right <= nums.length && nums[left] == target && nums[right] == target){
                return new int[]{left,right};
            }
            return new int[]{-1,-1};
        }

        private int binarySearch(int[] nums, int target,boolean leftTag){
            int left = 0, right = nums.length-1,ans = nums.length;
            while (left<=right){
                int mid = (right+left )>>1;
                if(nums[mid] > target || (leftTag && nums[mid]>=target)){
                    right = mid-1;
                    ans = mid;
                }else {
                    left = mid+1;
                }
            }
            return ans;
        }

//        /**
//         * 我的做法是直接先二分找到目标值的下标，然后向左右两侧扩散找到对应的起止下标
//         * @param nums
//         * @param target
//         * @return
//         */
//        public int[] searchRange(int[] nums, int target) {
//            if (nums.length == 0)
//                return new int[]{-1, -1};
//            int[] arr = new int[2];
//            int l = 0, r = nums.length - 1;
//            int targetindex = -1;
//            while (l <= r) {
//                int mid = l + r + 1 >> 1;
//                if (nums[mid] < target) {
//                    l = mid + 1;
//                } else if (nums[mid] > target) {
//                    r = mid - 1;
//                } else {
//                    targetindex = mid;
//                    break;
//                }
//            }
////            targetindex = nums[l] == target ? l : targetindex;
////            targetindex = nums[r] == target ? r : targetindex;
//            if (targetindex != -1) {
//                l = targetindex;
//                r = targetindex;
//                while (l >= 0 && nums[l] == target) {
//                    l = l - 1;
//                }
//                while (r <= nums.length - 1 && nums[r] == target) {
//                    r = r + 1;
//                }
//                arr[0] = l + 1;
//                arr[1] = r - 1;
//            } else {
//                arr[0] = -1;
//                arr[1] = -1;
//            }
//            return arr;
//        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}